Напиши програм који брзо може да утврди колико у датим интервалима природних бројева има простих.

Улаз

Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 10000\)) који представља број интервала, затим, у наредних \(n\) линија по два броја \(a\) и \(b\) (\(1 \leq a < b \leq 10^6\)) који представљају крајеве затвореног интервала \([a, b]\).

Излаз

На стандардни излаз исписати \(n\) природних бројева (сваки у посебној линији) који представљају број простих бројева у сваком интервалу \([a, b]\).

Пример

Улаз

3
1 100
100 1000
1000 10000

Излаз

25
143
1061